package com.mj.Tree;

import java.util.Comparator;

/**
 * @Author: LDeng
 * @Date: 2021-03-08 14:16
 */
public class BalanceBinarySearchTree<E> extends BinarySearchTree<E> {

    public BalanceBinarySearchTree() {
        this(null);
    }

    public BalanceBinarySearchTree(Comparator<E> comparator) {
        super(comparator);
    }

    protected void rotateLeft(Node<E> grand){//节点左旋转
        Node<E> p=grand.right;
        Node<E> child=p.left;
        //更新g的右节点和p的左节点
        grand.right=child;
        p.left=grand;

        afterRotate(grand,p,child);
    }

    protected void rotateRight(Node<E> grand){
        Node<E> p=grand.left;
        Node<E> child=p.right;
        grand.left=child;
        p.right=grand;
        afterRotate(grand,p,child);
    }

    protected void afterRotate(Node<E> grand,Node<E> p,Node<E> child) {
        //更新p,g 的parent属性( 双向 )
        p.parent = grand.parent;
        if (grand.isLeftChind()) {//g是父节点的左节点
            grand.parent.left = p;
        } else if (grand.isRightChild()) {//g是父节点的右节点
            grand.parent.right = p;
        } else {//父节点是空，g是根节点
            root = p;//根节点指向p
        }
        //更新p左子节点的parent
        if (child != null) {
            child.parent = grand;
        }
        //更新g的parent
        grand.parent = p;
    }



    protected void rotate(Node<E> r,//这些子树的根节点
                        Node<E> a, Node<E> b, Node<E> c,
                        Node<E> d,
                        Node<E> e, Node<E> f, Node<E> g) {
        d.parent = r.parent;
        //让d成为子树的根节点
        if (r.isLeftChind()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        //a-b-c
        b.left = a;
        if (a != null) {
            a.parent = b;
        }
        b.right = c;
        if (c != null) {
            c.parent = b;
        }

        //e-f-g
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        f.right = g;
        if (g != null) {
            g.parent = f;
        }

        //b-d-f
        d.left = b;
        b.parent = d;
        d.right = f;
        f.parent = d;

    }



}
